class Symbol:
    def __init__(self, kind, identifier_type, name, num_params=None):
        self.kind = kind
        self.type = identifier_type
        self.name = name
        self.num_params = num_params


class SymbolTable:
    def __init__(self):
        self.table = {}

    def insert(self, symbol):
        if symbol.name in self.table:
            raise ValueError(f"Semantic Error: Identifier '{symbol.name}' has already been declared.")
        self.table[symbol.name] = symbol

    def lookup(self, name):
        if name not in self.table:
            raise ValueError(f"Semantic Error: Identifier '{name}' is not declared.")
        return self.table[name]


class NodeType:
    PROGRAM = "Program"
    ID = "ID"
    DECLARATIONS = "Declarations"
    ID_LIST = "IDList"
    STATEMENT_LIST = "StatementList"
    STATEMENT = "Statement"
    EXPRESSION = "Expression"
    TERM = "Term"
    EXPR = "Expr"
    OP = "Op"
    INTC = "INTC"


class TreeNode:
    def __init__(self, node_type, value=None, children=None):
        self.node_type = node_type
        self.value = value
        self.children = children if children else []


def build_tree(input_list):
    stack = []
    root = None
    for line in input_list:
        level = line.count(" ") // 2
        node_type, value = line.strip().split(":", 1)
        value = value.strip() if value else None
        node = TreeNode(node_type, value)

        while len(stack) > level:
            stack.pop()

        if stack:
            parent = stack[-1]
            parent.children.append(node)
        else:
            root = node

        stack.append(node)

    return root


def build_symbol_table(node, symbol_table):
    if node.node_type == NodeType.ID_LIST:
        for child in node.children:
            name = child.value
            symbol = Symbol("Variable", "INT", name)
            symbol_table.insert(symbol)
    for child in node.children:
        build_symbol_table(child, symbol_table)


def check_semantics(node, symbol_table):
    if node.node_type == NodeType.STATEMENT:
        check_statement_semantics(node, symbol_table)
    for child in node.children:
        check_semantics(child, symbol_table)


def check_statement_semantics(node, symbol_table):
    id_node = node.children[0]
    expression_node = node.children[1]
    id_name = id_node.value

    try:
        id_symbol = symbol_table.lookup(id_name)
    except ValueError as e:
        print(e)
        return

    expression_type = get_expression_type(expression_node, symbol_table)
    if id_symbol.type != expression_type:
        print(
            f"Semantic Error: Type mismatch in assignment, "
            f"trying to assign '{expression_type}' to '{id_symbol.type}' variable '{id_name}'"
        )


def get_expression_type(node, symbol_table):
    if node.node_type == NodeType.TERM:
        return get_term_type(node, symbol_table)
    return "INT"  # 默认为整数类型


def get_term_type(node, symbol_table):
    if node.children[0].node_type == NodeType.ID:
        id_name = node.children[0].value
        try:
            id_symbol = symbol_table.lookup(id_name)
            return id_symbol.type
        except ValueError as e:
            print(e)
            return None
    elif node.children[0].node_type == NodeType.INTC:
        return "INT"
    elif node.children[0].node_type == NodeType.EXPR:
        return get_expression_type(node.children[0], symbol_table)
    return None


def main():
    input_list = [
        'Program: example',
        '  Declarations:',
        '    IDList:',
        '      ID: a',
        '      ID: b',
        '      ID: c',
        '  StatementList:',
        '    Statement:',
        '      ID: a',
        '      Expression:',
        '        Term:',
        '          ID: b',
        '        Op: +',
        '        Term:',
        '          ID: c',
        '          Op: *',
        '          INTC: 2',
        '        Op: -',
        '        Term:',
        '          INTC: 4',
        '    Statement:',
        '      ID: b',
        '      Expression:',
        '        Term:',
        '          Expr:',
        '            Expression:',
        '              Term:',
        '                ID: a',
        '              Op: +',
        '              Term:',
        '                INTC: 1',
        '          Op: *',
        '          INTC: 3',
    ]
    input_tree_with_error = [
        'Program:',
        '  ID: example',
        '  Declarations:',
        '    IDList:',
        '      ID: a',
        '      ID: b',
        '      ID: c',
        '  StatementList:',
        '    Statement:',
        '      ID: a',
        '      Expression:',
        '        Term:',
        '          ID: b',
        '        Op: +',
        '        Term:',
        '          ID: c',
        '          Op: *',
        '          INTC: 2',
        '        Op: -',
        '        Term:',
        '          INTC: 4',
        '    Statement:',
        '      ID: b',
        '      Expression:',
        '        Term:',
        '          Expr:',
        '            Expression:',
        '              Term:',
        '                ID: a',
        '              Op: +',
        '              Term:',
        '                INTC: 1',
        '          Op: *',
        '          INTC: 3',
        '    Statement:',  # 错误：未声明的标识符 'd'
        '      ID: d',
        '      Expression:',
        '        Term:',
        '          ID: a',
        '        Op: +',
        '        Term:',
        '          INTC: 2'
    ]

    input_tree_duplicate_id = [
        'Program:',
        '  ID: example',
        '  Declarations:',
        '    IDList:',
        '      ID: a',
        '      ID: b',
        '      ID: a',  # 错误：重复定义的标识符 'a'
        '  StatementList:',
        '    Statement:',
        '      ID: a',
        '      Expression:',
        '        Term:',
        '          INTC: 2'
    ]

    input_tree_wrong_assignment = [
        'Program:',
        '  ID: example',
        '  Declarations:',
        '    IDList:',
        '      ID: a',
        '      ID: b',
        '  StatementList:',
        '    Statement:',
        '      ID: a',
        '      Expression:',
        '        Term:',
        '          INTC: 1',
        '    Statement:',  # 错误：赋值语句左端不是变量标识符
        '      INTC: 2',
        '      Expression:',
        '        Term:',
        '          ID: a'
    ]

    input_tree_wrong_procedure_call = [
        'Program:',
        '  ID: example',
        '  Declarations:',
        '    IDList:',
        '      ID: a',
        '      ID: b',
        '  StatementList:',
        '    Statement:',
        '      ID: a',
        '      Expression:',
        '        Term:',
        '          INTC: 1',
        '    Statement:',  # 错误：过程调用语句中，标识符不是过程标识符
        '      ProcCall:',
        '        ID: a'
    ]

    root = build_tree(input_tree_with_error)
    symbol_table = SymbolTable()
    build_symbol_table(root, symbol_table)
    check_semantics(root, symbol_table)


if __name__ == "__main__":
    main()

